package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-12-20
 * 不同路径
 */
public class UniquePaths {

    /**
     * 主
     * \
     * 输入：m = 3, n = 7
     * 输出：28
     * \
     * 输入：m = 3, n = 2
     * 输出：3
     * 解释：
     * 从左上角开始，总共有 3 条路径可以到达右下角。
     * 1. 向右 -> 向下 -> 向下
     * 2. 向下 -> 向下 -> 向右
     * 3. 向下 -> 向右 -> 向下
     * \
     * @param args args
     */
    public static void main(String[] args) {
        UniquePaths uniquePaths = new UniquePaths();
        int m = 3, n = 7;
        System.out.println(uniquePaths.uniquePaths(m, n));
    }

    /**
     * 独特路径
     * 动态规划
     * @param m m
     * @param n n
     * @return int
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //初始化边界值
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int j = 0; j < m; j++) {
            dp[j][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //目的地dp[i][j]到达所花费的总路径，类似杨辉三角形
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}
